package com.zjsru.plan2024.oneday;

import java.util.Arrays;

/**
 * 1673. 找出最具竞争力的子序列
 * @Author: cookLee
 * @Date: 2024-05-24
 */
public class MostCompetitive {

    /**
     * 主
     * \
     * 输入：nums = [3,5,2,6], k = 2
     * 输出：[2,6]
     * 解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。
     * \
     * 输入：nums = [2,4,3,3,5,4,9,6], k = 4
     * 输出：[2,3,3,4]
     * \
     * @param args args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{3, 5, 2, 6};
        int k = 2;
        MostCompetitive mostCompetitive = new MostCompetitive();
        System.out.println(Arrays.toString(mostCompetitive.mostCompetitive(nums, k)));
    }

    /**
     * 最具竞争力
     *
     * @param nums nums
     * @param k    k
     * @return {@link int[]}
     */
    public int[] mostCompetitive(int[] nums, int k) {
        int len = nums.length;
        //设置栈长度
        int stackLen = 0;
        //模拟栈
        int[] stack = new int[k];
        for (int i = 0; i < len; i++) {
            int curr = nums[i];
            //循环压栈，满足条件1.栈不为空 2.栈顶元素大于当前元素 3.栈大小+剩余元素大于目标K，这样可以找最接近可替换的栈下标
            while(stackLen > 0 && stack[stackLen - 1] > curr && (stackLen + len - i) > k ){
                //出栈
               stackLen--;
            }
            if(stackLen < k){
                //入栈
                stack[stackLen] = curr;
                stackLen++;
            }
        }
        return stack;
    }

}
